{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "# 第二章.贪心算法\n",
    "\n",
    "## 背包问题\n",
    "<p>算法思想:首先计算物品的单位重量的价值,然后按照单位重量的价值由大到小排序,只要没有到达背包承载的重量，就装入,直到物品i装不下时或物品已全部装入背包时。如果物品全部装入背包,那么算法结束,否则从物品i分割出部分装入背包,把背包装满,算法结束</p>"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "物品编号:3,放入重量:2,放入的价值:8\n",
      "物品编号:0,放入重量:2,放入的价值:4\n",
      "物品编号:4,放入重量:1,放入的价值:2\n",
      "物品编号:1,放入重量:1,放入的价值:0.75\n",
      "总价的价值为:14.75\n"
     ]
    }
   ],
   "source": [
    "def knapsack(capacity=0,goods_set=[]):\n",
    "    # 按照单位价值排序\n",
    "    goods_set.sort(key=lambda goods:goods[1]/goods[2],reverse=True) #按照单位物品价值从大到小排序\n",
    "    result = [] # 装入背包的物品集\n",
    "    sum_v = 0 #装入背包的价值\n",
    "    for goods in goods_set:\n",
    "        if capacity < goods[2]: # 装不下时的处理\n",
    "            # (物品编号,放入价值,物品重量)\n",
    "            result.append([goods[0],goods[1]/goods[2]*capacity,capacity]) # 分割一部分装入\n",
    "            sum_v+=capacity*goods[1]/goods[2] # 统计装入部分价值\n",
    "            break\n",
    "\n",
    "        result.append(goods) # 装入\n",
    "        sum_v+=goods[1] # 统计装入部分价值\n",
    "        capacity-=goods[2] #  重新计算背包剩余的承载重量\n",
    "    return result,sum_v\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # (物品编号,物品价值,物品重量)\n",
    "    some_goods = [(0,4,2),(1,6,8),(2,3,5),(3,8,2),(4,2,1)]\n",
    "    res,sum_v = knapsack(6,some_goods)\n",
    "    for goods in res:\n",
    "        print(\"物品编号:\"+str(goods[0])+',放入重量:'+str(goods[2])+',放入的价值:'+str(goods[1]))\n",
    "    print('总价的价值为:'+str(sum_v))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-09-25T13:14:30.182182Z",
     "start_time": "2023-09-25T13:14:30.176132100Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 最小生成树(克鲁斯卡尔算法)\n",
    "<p>克鲁斯卡尔算法的思想是:权最小的边优先检查，若他的两个端点不在一连通分支,则将该边加入到最小生成树中,否则,放弃，当加入n-1条边后,最小生成树完毕,结束算法。</p>"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1, 3, 1)\n",
      "(4, 6, 2)\n",
      "(2, 5, 3)\n",
      "(3, 6, 4)\n",
      "(2, 3, 5)\n"
     ]
    }
   ],
   "source": [
    "def kruskal(edge_list,vertexs):\n",
    "    vertex_num = len(vertexs)\n",
    "    edge_num = len(edge_list)\n",
    "    tree_mst = []\n",
    "    if vertex_num <=0 or edge_num<vertex_num-1:\n",
    "        return tree_mst\n",
    "    edge_list.sort(key=lambda a:a[2]) # 按照边权由小到大排序\n",
    "    group = [[i] for i in range (1,vertex_num+1)]\n",
    "    for edge in edge_list:\n",
    "        k = len(group) # 获取分支数目\n",
    "        if k ==1: # 如果只有一个分支,则跳出循环,算法结束\n",
    "            break\n",
    "        for i in range(k): # 判断两个端点所属的分支\n",
    "            if edge[0] in group[i]:\n",
    "                m = i\n",
    "            if edge[1] in group[i]:\n",
    "                n = i\n",
    "        if m !=n: #若不在同一个分支\n",
    "            tree_mst.append(edge) # 将边加入到最小生成树中\n",
    "            group[m]=group[m]+group[n] # 合并分支\n",
    "            group.remove(group[n])\n",
    "    return tree_mst\n",
    "\n",
    "\n",
    "edge_list = [(1,2,6),(1,3,1),(1,4,5),(2,3,5),(2,5,3),(3,4,5),(3,6,4),(3,5,6),(4,6,2),(5,6,6)]\n",
    "vertexs = [1,2,3,4,5,6]\n",
    "tree_mst = kruskal(edge_list,vertexs)\n",
    "for edge in tree_mst:\n",
    "    print(edge)"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-09-26T13:05:25.944103900Z",
     "start_time": "2023-09-26T13:05:25.936109600Z"
    }
   }
  },
  {
   "cell_type": "markdown",
   "source": [
    "## 活动安排\n",
    "<p>问题描述:假设现在有一批活动，他们都需要借用一间教室。他们的活动时间不一样。请问如何让活动个数最多</p\n",
    "<p>贪心算法的思路是:先将活动按照活动结束时间从低到高排列,然后逐个选择活动开始时间大于活动结束时间的活动</p>"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "活动安排:\n",
      "第4号活动\n",
      "第5号活动\n",
      "第3号活动\n",
      "第6号活动\n",
      "总共安排的活动数: 4\n"
     ]
    }
   ],
   "source": [
    "def meeting_Greedy_Select(meetings):\n",
    "    length = len(meetings) # 活动个数\n",
    "    meetings.sort(key=lambda x:x[2]) # 按照活动结束时间从小到大排列\n",
    "    j = 0 # 标记活动\n",
    "    result = [] # 装入活动\n",
    "    result.append(meetings[0]) # 装入第一项活动\n",
    "    for i in range(length):\n",
    "        if meetings[i][1] >meetings[j][2]: # 下个活动的开始时间大于本次活动的结束时间\n",
    "            j = i # 开始这次活动\n",
    "            result.append(meetings[j])\n",
    "    return result\n",
    "\n",
    "meetings = [(4,1,4),(2,3,5),(1,0,6),(5,5,7),(7,3,8),(8,5,9),(9,6,10),(3,8,11),(10,8,12)\n",
    "            ,(11,2,13),(6,12,14)\n",
    "            ]\n",
    "\n",
    "res = meeting_Greedy_Select(meetings)\n",
    "print(\"活动安排:\")\n",
    "len = len(res) # 活动总个数\n",
    "for meeting in res:\n",
    "    print('第'+str(meeting[0])+'号活动')\n",
    "\n",
    "print(\"总共安排的活动数:\",str(len))"
   ],
   "metadata": {
    "collapsed": false,
    "ExecuteTime": {
     "end_time": "2023-09-27T12:48:49.219555800Z",
     "start_time": "2023-09-27T12:48:49.159558200Z"
    }
   }
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "outputs": [],
   "source": [],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
